#ifndef CVX_QUAD_TREE_H
#define CVX_QUAD_TREE_H 1

#include "cvxImage.h"
#include <vector>
#include <map>
#include <list>

using std::vector;
using std::map;
using std::list;

//quad tree in image space

//-------------------------------------------------------------------------------
//  Generic quadtree cell. Note that the locational codes and the cell level are 
//  only used in neighbor searching; they are not necessary for point or region 
//  location.
//-------------------------------------------------------------------------------
class QtNode 
{
public:
	unsigned int    _xLocCode;   // X locational code
	unsigned int    _yLocCode;   // Y locational code
	unsigned int    _level;      // Cell level in hierarchy (smallest cell has level 0)
	QtNode  *_parent;       // Pointer to parent cell
	QtNode  *_children[4];  // Pointer to first of 4 contiguous child cells
	void    *_data;        // Application specific cell data

	//root
	QtNode();
	void createChildrenNode();
	void set(bool xRight, bool yBottom, QtNode *parent);
	bool similarColor();
	bool isLeaf() const;
	inline int size() {return (1<<_level);}
};

struct QtData
{
	int _idx;    // index, -1 for already known shading value
	double _s;    //shading value, 0 for unknown pixel (areas)
	unsigned char _r, _g, _b;  //color value
	unsigned char _l;          //0.3 0.59 0.11 or rgb
	bool _edge;                //whether this patch is on the edge area or not
	double _minSha;            //minimal shading min(s*1.2, 0.95)
	int _nodeIdx;              //node index
	float _avector[3];         //A vector to interpolate, r, g, b order
//	float _stddev[3];             //standard deviation in this node
	QtNode *_bestMatchNode;     //used in stereoscopic intrinsic recovery, for corresponding nodes in the left and right images
    int _similarRefIdx;         //similar reflectance color index -1 for no similar

	QtData()
	{
		_bestMatchNode = NULL;
		_similarRefIdx = -1;
	}

	void copy(const QtData *d)
	{
		assert(d);
		_idx = d->_idx;
		_s = d->_s;
		_r = d->_r, _g = d->_g, _b = d->_b;
		_l = d->_l, _edge = d->_edge;
		_minSha = d->_minSha;
		_nodeIdx = d->_nodeIdx;
		_avector[0] = d->_avector[0];
		_avector[1] = d->_avector[1];
		_avector[2] = d->_avector[2];
		_similarRefIdx = d->_similarRefIdx;
	}
	
	//find color difference within a threshold
	int difColor(const QtData *d, float threshold)
	{
		assert(d);
		int dif_r = abs((int)_r - d->_r);
		int dif_g = abs((int)_g - d->_g);
		int dif_b = abs((int)_b - d->_b);
		if(dif_r <= threshold && dif_g <= threshold && dif_b <=threshold)
		{
			return dif_r + dif_g + dif_b;
		}
		else
		{
			return (1<<10);
		}
	}

	
};

struct S_EdgeEquationData 
{
	int idx[3];
	unsigned char lum[3];  //luminance
	double sha[3];         //shading
};

//base class of Quad tree
class CvxQuadTree
{
public:
	CvxQuadTree(unsigned int levels);
	virtual ~CvxQuadTree();	
	virtual void create(QtNode * node);
	virtual void balance();
	
	virtual void cloneTree(const QtNode * orgNode, QtNode *dNode);//clone quad tree	

	//locate position (x, y) in the node of Quadtree, NULL for out of range
	virtual QtNode *LocateNode (int x, int y);
	virtual QtNode *LocateLeftNeighbor(QtNode *cell);
	virtual QtNode *LocateBottomNeighbor(QtNode *cell);

	virtual QtNode *LocateRightNeighbor (QtNode *cell);
	virtual QtNode *LocateTopNeighbor(QtNode *cell);

	//0, 1 or 2 neighbors 
	virtual int leftNeighbors(QtNode *cell, QtNode *&n1, QtNode *&n2);
	virtual int bottomNeighbors(QtNode *cell, QtNode *&n1, QtNode *&n2);
	virtual int rightNeighbors(QtNode *cell, QtNode *&n1, QtNode *&n2);
	virtual int topNeighbors(QtNode *cell, QtNode *&n1, QtNode *&n2);

	//construct a restricted quad tree from a common quad tree
	//node == NULL for start from root
	virtual void ConstructRestrictedQuadTree(QtNode *node, bool& changed);
	void leafNumber(QtNode *node, int &number);
	void pixelLeafNumber(QtNode *node, int &number);

	//get tree level from the maximal length of width or height
	static unsigned int GetLevel(unsigned int length);
	static void GatherData(CvxQuadTree * const pTree, QtNode *cNode, double M[][3], 
					   vector<unsigned int> &idxVec, vector<double> &shadingVVec, vector<unsigned int> &szVec, bool isNodeIdx);
	static void GatherNeighborData(QtNode *leafNode, double M[][3], vector<unsigned int> &idces, 
							   vector<double> &shadingVVec, vector<unsigned int> &szVec, bool isNodeIdx);

protected:
	
	inline void GetCommonAncestor(QtNode *&cell, unsigned int &cellLevel, unsigned int binaryDiff);
	inline void TraverseToLevel(QtNode *&cell, unsigned int &nextLevel, 
							    unsigned int xLocCode, unsigned int yLocCode, unsigned int level);
	inline void TraverseToPosition(QtNode *&cell, unsigned int &nextLevel, 
								   unsigned int xLocCode, unsigned int yLocCode);
	//subdivide a cell
	void SubdivideNode(QtNode *cell);

public:

	const int m_N_LEVELS;
	const int m_ROOT_LEVEL; //root level = levels - 1
	const int m_MAX_VAL;    //max val = 1<< root_level	
	QtNode *m_root;         //tree node
	int m_nodeNum;          //total node number
};









//-------------------------------------------------------------------------------
//  Macro for traversing a quadtree to a common ancestor of a specified cell 
//  and its neighbor, whose x or y locational code differs from the cell's
//  corresponding x or y locational code by binaryDiff (determined by XOR'ing the 
//  appropriate pair of x or y locational codes). Upon entering, cell is the 
//  specified cell and cellLevel is the cell's level. Upon termination, cell is 
//  the common ancestor and cellLevel is the common ancestor's level.
//-------------------------------------------------------------------------------
inline void CvxQuadTree::GetCommonAncestor(QtNode *&cell, unsigned int &cellLevel,
										   unsigned int binaryDiff)                         
{                                                                                 
	while ((binaryDiff) & (1 << (cellLevel)))
	{    
		assert(cell);
		cell = (cell)->_parent; 		
		(cellLevel)++;                                                            
	}                                                                            
}
//-------------------------------------------------------------------------------
//  Macro to traverse a quadtree from a specified cell to an offspring cell by 
//  following the x and y locational codes, xLocCode and yLocCode. The offpring 
//  cell is either at a specified level or is a leaf cell if a leaf cell is 
//  reached before the specified level. Upon entering, cell is the specified 
//  cell and nextLevel is one less than the level of the specified cell. Upon 
//  termination, cell is the offspring cell and nextLevel is one less than the 
//  level of the offspring cell.
//-------------------------------------------------------------------------------

inline void CvxQuadTree::TraverseToLevel(QtNode *&cell, unsigned int &nextLevel, 
										 unsigned int xLocCode, unsigned int yLocCode, unsigned int level)              
{
	unsigned int n = nextLevel - level + 1;                                   
	while (n--) 
	{
		unsigned int childBranchBit = 1 << (nextLevel);                           
		unsigned int x_index = (xLocCode & childBranchBit) >> nextLevel;
		unsigned int y_index = (yLocCode & childBranchBit) >> nextLevel; 
		--nextLevel;
		unsigned int childIndex = x_index + y_index*2;
		cell = cell->_children[childIndex];
		if (!cell) break;
		if (cell->isLeaf()) break;            //leaf                                 
	}                                                                             
}

//-------------------------------------------------------------------------------
//  Macro to traverse a quadtree from a specified cell (typically the root cell) 
//  to a leaf cell by following the x and y locational codes, xLocCode and 
//  yLocCode. Upon entering, cell is the specified cell and nextLevel is one less 
//  than the level of the specified cell. Upon termination, cell is the leaf cell
//  and nextLevel is one less than the level of the leaf cell. 
//-------------------------------------------------------------------------------
inline void CvxQuadTree::TraverseToPosition(QtNode *&cell, unsigned int &nextLevel, 
											unsigned int xLocCode,unsigned int yLocCode)
{         
	while (cell && !cell->isLeaf()) {                                                    
		unsigned int childBranchBit = 1 << (nextLevel);                           	
		unsigned int x_index = (xLocCode & childBranchBit) >> nextLevel;
		unsigned int y_index = (yLocCode & childBranchBit) >> nextLevel;
		--nextLevel;
		unsigned int childIndex = x_index + y_index*2;
		cell = cell->_children[childIndex];
	}         
}


#endif